翻訳と辞書 Words near each other ・ Randomajestiq ・ Randominta ・ Randomization ・ Randomization function ・ Randomized algorithm ・ Randomized algorithms as zero-sum games ・ Randomized block design ・ Randomized controlled trial ・ Randomized experiment ・ Randomized Hough transform ・ Randomized meldable heap ・ Randomized response ・ Randomized rounding ・ Randomized weighted majority algorithm ・ Randomness ・ Randomness extractor ・ Randomness merger ・ Randomness tests ・ Random—Burin—St. George's ・ Randon ・ Randonnai ・ Randonneuring ・ Randonneurs USA ・ Randonnée ・ Randoon ・ Randor ・ Randor Bierd ・ Randor Guy ・ Randori ・ Randori (album) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Randomness extractor ： ウィキペディア英語版 Randomness extractor A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weakly random entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the source and uniformly distributed. Examples of weakly random sources include radioactive decay or thermal noise; the only restriction on possible sources is that there is no way they can be fully controlled, calculated or predicted, and that a lower bound on their entropy rate can be established. For a given source, a randomness extractor can even be considered to be a true random number generator (TRNG); but there is no single extractor that has been proven to produce truly random output from any type of weakly random source. Sometimes the term "bias" is used to denote a weakly random source's departure from uniformity, and in older literature, some extractors are called unbiasing algorithms,〔David K. Gifford, Natural Random Numbers, MIT/LCS/TM-371, Massachusetts Institute of Technology, August 1988.〕 as they take the randomness from a so-called "biased" source and output a distribution that appears unbiased. The weakly random source will always be longer than the extractor's output, but an efficient extractor is one that lowers this ratio of lengths as much as possible, while simultaneously keeping the seed length low. Intuitively, this means that as much randomness as possible has been "extracted" from the source. Note that an extractor has some conceptual similarities with a pseudorandom generator (PRG), but the two concepts are not identical. Both are functions that take as input a small, uniformly random seed and produce a longer output that "looks" uniformly random. Some pseudorandom generators are, in fact, also extractors. (When a PRG is based on the existence of hard-core predicates, one can think of the weakly random source as a set of truth tables of such predicates and prove that the output is statistically close to uniform.〔(【引用サイトリンク】 title= Extractors and Pseudorandom Generators )〕) However, the general PRG definition does not specify that a weakly random source must be used, and while in the case of an extractor, the output should be statistically close to uniform, in a PRG it is only required to be computationally indistinguishable from uniform, a somewhat weaker concept. NIST Special Publication 800-90B (draft) recommends several extractors, including the SHA hash family and states that if the amount of entropy input is twice the number of bits output from them, that output can be considered essentially fully random.〔(Recommendation for the Entropy Sources Used for Random Bit Generation (draft) NIST SP800-90B ), Barker and Kelsey, August 2012, Section 6.4.2〕 ==Formal definition of extractors== The min-entropy of a distribution $X$ (denoted $H\_(X)$), is the largest real number $k$ such that $\backslash Pr(=x)\; \backslash leq\; 2^$ for every $x$ in the range of $X$. In essence, this measures how likely $X$ is to take its most likely value, giving a worst-case bound on how random $X$ appears. Letting $U\_$ denote the uniform distribution over $\backslash ^$, clearly $H\_(U\_)\; =\; \backslash ell$. For an ''n''-bit distribution $X$ with min-entropy ''k'', we say that $X$ is an $(n,\; k)$ distribution. Definition (Extractor): (''k'', ''ε'')-extractor Let $\backslash text:\; \backslash ^n\; \backslash times\; \backslash ^d\; \backslash to\; \backslash ^m$ be a function that takes as input a sample from an $(n,\; k)$ distribution $X$ and a ''d''-bit seed from $U\_d$, and outputs an ''m''-bit string. $\backslash text$ is a (''k'', ''ε'')-extractor, if for all $(n,\; k)$ distributions $X$, the output distribution of $\backslash text$ is ''ε''-close to $U\_m$. In the above definition, ''ε''-close refers to statistical distance. Intuitively, an extractor takes a weakly random ''n''-bit input and a short, uniformly random seed and produces an ''m''-bit output that looks uniformly random. The aim is to have a low $d$ (i.e. to use as little uniform randomness as possible) and as high an $m$ as possible (i.e. to get out as many close-to-random bits of output as we can). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Randomness extractor」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.